// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-21 10:56
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.swapNodes_;

import com.DataStruct.LinkList.ListNode;

public class swapNodes_ {
    // 交换单链表中的节点并且返回链表的头结点
    public ListNode swapNodes(ListNode head, int k) {
        // 前k个节点的位置可以简单的定位，但是从单链表尾部定位后k个节点时候需要使用辅助指针进行定位
        ListNode p = head, q = head;
        ListNode kNode = head;
        int tmp;
        int i = 1;
        while (p.next != null) {
            // 当p指针到达链表尾节点的时候，q指针刚好指向链表尾部第k个节点
            p = p.next;
            ++i;
            if (i == k) {
                // 存储开头第k个节点
                kNode = p;
            }
            if (i > k) {
                q = q.next;
            }
        }
        tmp = kNode.val;
        kNode.val = q.val;
        q.val = tmp;
        return head;
    }
}
